package algorithms.sort;

/**
 * 快速排序<br>
 *
 * <br>特点：<br>
 * 1 原地排序<br>
 * 2 将长度为N的数组排序所需的时间和NlgN成正比<br>
 *
 */
public class QuickSort {

	
	public static void sort(Comparable[] a){
		sort(a, 0, a.length - 1);
	}
	
	private static void sort(Comparable[] a, int lo, int hi){
		if(hi <= lo) 	return;
		int j = partition(a, lo, hi);
		sort(a, lo, j - 1);
		sort(a, j + 1, hi);
	}
	
	
	//切分
	private static int partition(Comparable[] a, int lo, int hi) {
		int i = lo, j = hi + 1;
		Comparable v = a[lo];
		while(true){
			while(less(a[++i], v)){
				if(i == hi)	break;
			}
			while(less(v, a[--j])){
				if(j == lo)	break;  //如果仅对于lo就是切分元素来说，这个判断是可以去掉的，因为不可能比自己小
			}
			if(i >= j)	break;	
			exch(a, i, j);
		}
		exch(a, lo, j);
		return j;
	}
	
	private static boolean less(Comparable v, Comparable w){
		return v.compareTo(w) < 0;
	}
	
	private static void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}

	public static void show(Comparable[] a){
		for(int i = 0; i < a.length; i++){
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		String a[]={"1","4","7","8","6","3","4","4","4","4","4","2","5","9","4","2"};
		QuickSort.sort(a);
		QuickSort.show(a);
		System.out.println("10".compareTo("2"));
		System.out.println("10".hashCode() + "," + "2".hashCode());
	}

}
